/**
 * 421. 数组中两个数的最大异或值
 * https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/
 */
public class Solutions_421 {
    public static void main(String[] args) {
        int[] nums = {3, 10, 5, 25, 2, 8};  // output: 28  {5 ^ 25 = 28}
        int result = findMaximumXOR(nums);
        System.out.println(result);
    }

    static Trie_421 root = null;
    static int len = 0;
    public static int findMaximumXOR(int[] nums) {
        if (nums == null) {
            return 0;
        }
        root = new Trie_421();
        // 找到 nums 中的最大数
        int max = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
        }
        // 最大数的位长度
        len = Integer.toBinaryString(max).length();
        buildTrie(nums);
        int res = helper(nums);
        return res;
    }

    /**
     * 构建二进制位的树
     * 例：3(00011)，25(11001)
     *                  root
     *                 /   \
     *                0     1
     *               /       \
     *              0         1
     *             /         /
     *            0         0
     *             \       /
     *              1     0
     *               \     \
     *                1     1
     * 建树规则：
     * 1. 两个节点，左节点为 0，右节点为 1
     * 2. 树的层次高度，取决于最大值（3 和 25 时，取 25，二进制位为 5），
     *      或者直接构建 32 位/层的树，可以表示 int 最大值
     */
    public static void buildTrie(int[] nums) {
        for (int num : nums) {
            Trie_421 cur = root;
            // 逐位遍历 num（从高位往低位遍历）
            for (int i = len - 1; i >= 0; i--) {
                // num 不会为负数，所以不需要无符号右移
                int bit = (num >> i) & 1;
                if (cur.childs[bit] == null) {
                    cur.childs[bit] = new Trie_421();
                }
                cur = cur.childs[bit];
            }
        }
    }

    /**
     * 遍历 nums 中每一个元素，找到另一个元素，可以组成最大的异或值
     * 例：3(00011)，25(11001)，构建成的树如下所示：
     *                  root
     *                 /   \
     * level1         0     1
     *               /       \
     * level2       0         1
     *             /         /
     * level3     0         0
     *             \       /
     * level4       1     0
     *               \     \
     * level5         1     1
     *
     * 遍历 3 时，
     * 第 1 位/层：位是 0，则查找 level1 是否存在节点 1
     *  若有，说明 nums 中存在至少一个元素，可以使异或值最少为：(10000)2
     * 第 2 位/层：位是 0，则查找 level2 是否存在节点 1
     *  若有，说明 nums 中存在至少一个元素：可以使异或值最少为：(11000)2
     * 第 3 位/层：位是 0，则查找 level3 是否存在节点 1
     *  若有，说明 nums 中存在至少一个元素：可以使异或值最少为：(11000)2
     *  若没有，则只能走节点 0
     * 第 4 位/层：位是 1，则查找 level4 是否存在节点 0
     *  若有，说明 nums 中存在至少一个元素：可以使异或值最少为：(11010)2
     * 第 5 位/层：位是 1，则查找 level5 是否存在节点 0
     *  若有，说明 nums 中存在至少一个元素：可以使异或值最少为：(11010)2
     */
    public static int helper(int[] nums) {
        int max = 0, max1 = -1, max2 = -1;
        for (int num : nums) {
            if (num == max1 || num == max2) {
                // 当前 num 已经计算出最大的异或值
                continue;
            }
            Trie_421 cur = root;
            int sum = 0;
            // 逐位遍历 num（从高位往低位遍历）
            for (int i = len - 1; i >= 0; i--) {
                int bit = (num >> i) & 1;
                // 计算 bit ^ ? = 1，等式可以转换成：? = bit ^ 1;
                int xorBit = bit ^ 1;
                if (cur.childs[xorBit] != null) {
                    // 前缀树中，cur 节点下存在位，可以异或生成 1
                    sum += (1 << i);
                    cur = cur.childs[xorBit];
                }  else {
                    // 没有可以进行异或操作，结果为 1 的位节点
                    cur = cur.childs[bit];
                }
            }
            if (sum > max) {
                // 记录下最大异或值，同时记录组成最大异或值的两个元素
                max = sum;
                max1 = num;
                max2 = max ^ max1;
            }
//            max = Math.max(max, sum);
        }
        return max;
    }
}

class Trie_421 {
    Trie_421[] childs = new Trie_421[2];
}
